﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace PushBox
{
    /// <summary>
    /// 广度优先搜索
    /// 搜索过程中将搜索过的局面从队列移除，将新的局面添加到队列的尾部
    /// 测试结果显示速度和传统广度优先搜索几乎相同（在不进行更新界面信息的操作及队列空间和搜索深度的统计时）
    /// 如果实时需要更新界面信息的话还是建议使用传统深度优先搜索
    /// </summary>
    class AutoSingleQueue : BaseAuto
    {
        public AutoSingleQueue(Action<string> handler) : base(handler)
        {
            //Backup(path);
        }

        private int Width;
        private int Depth;
        private const string path = "AutoSingleQueue.solve";

        public override List<int> Run(Game game)
        {
            var st = Stopwatch.StartNew();
            var state = RunMain(game);
            st.Stop();
            List<int> paths = state?.GetPaths();
            var lines = new List<string> {
                $"关卡{game.Level}:",
                game.MapData
            };

            if(paths == null)
            {
                if(state != null)
                {
                    Info = string.Format("〓〓 超过1分钟结束,搜索深度{0},队列峰值{1},耗时{2}", Depth, Width, st.Elapsed);
                    File.AppendAllText("map-hards.txt", $"{game.MapData}\r\n");
                }
                else
                {
                    Info = string.Format("✖✖ 无解,搜索深度{0},队列峰值{1},耗时{2}", Depth, Width, st.Elapsed);
                    File.AppendAllText("map-nosolvers.txt", $"{game.MapData}\r\n");
                }
            }
            else
            {
                Info = string.Format("✔✔ 最优解{0}步,队列峰值{1},耗时{2}", paths.Count, Width, st.Elapsed);
                var str = string.Join("", paths.Select(x => x == 0 ? "左" : x == 1 ? "上" : x == 2 ? "右" : "下"));
                lines.Add(str);

                File.AppendAllText("map-solvers.txt", $"{game.MapData};{paths.Count}\r\n");
            }
            lines.Add(Info);
            lines.Add(spLine);
            File.AppendAllLines(path, lines);

            this.handler?.Invoke(Info);
            return paths;
        }

        private GameState RunMain(Game game)
        {
            Width = 0;
            var state = new GameState(game);
            var visitedStates = new List<string> { state.ToString() };
            var states = new Queue<GameState>();
            states.Enqueue(state);
            var st = Stopwatch.StartNew();

            while(states.Any())
            {
                GameState stt = states.Dequeue();
                if(stt == null)
                {
                    break;
                }

                //if(!Maps.RunHard && st.ElapsedMilliseconds > 60000)
                //{
                //    st.Stop();
                //    return new GameState();
                //}

                if(Depth != stt.Depth)
                {
                    Depth = stt.Depth;
                    //this.handler?.Invoke(string.Format("深度{0},队列峰值{1},当前队列{2}", Depth, Width, states.Count));
                }

                for(var dir = 0; dir < 4; dir++)
                {
                    if(stt.LastDir != -1 && !stt.HasPush && Math.Abs(stt.LastDir - dir) == 2)
                    {
                        continue;
                    }

                    var newState = stt.Move(dir);
                    if(newState != null)
                    {
                        var str = newState.ToString();
                        if(visitedStates.Contains(str))
                        {
                            continue;
                        }
                        if(newState.Check())
                        {
                            return newState;
                        }
                        visitedStates.Add(str);
                        var hasDeath = newState.IsDeath();
                        if(!hasDeath)
                        {
                            states.Enqueue(newState);
                            if(states.Count > Width)
                            {
                                Width = states.Count;
                            }
                        }
                    }
                }
            }
            return null;
        }

        public override void Stop()
        {

        }
    }
}